Công thức Nguyên lý bao hàm-loại trừ

Trong công thức tổng quát của nó, nguyên lý bao hàm-loại trừ phát biểu rằng với n tập hợp hữu hạn A1, …, An, ta có định thức sau:

| ⋃ i = 1 n A i | = ∑ i = 1 n | A i | − ∑ 1 ⩽ i < j ⩽ n | A i ∩ A j | + ∑ 1 ⩽ i < j < k ⩽ n | A i ∩ A j ∩ A k | − ⋯ + ( − 1 ) n + 1 | A 1 ∩ ⋯ ∩ A n | . {\displaystyle \left|\bigcup _{i=1}^{n}A_{i}\right|=\sum _{i=1}^{n}|A_{i}|-\sum _{1\leqslant i<j\leqslant n}|A_{i}\cap A_{j}|+\sum _{1\leqslant i<j<k\leqslant n}|A_{i}\cap A_{j}\cap A_{k}|-\cdots +(-1)^{n+1}\left|A_{1}\cap \cdots \cap A_{n}\right|.}

 

 

 

 

(1)

Mỗi phần tử trong công thức bao hàm-loại trừ dần dần sửa giá trị đếm cho đến khi mỗi vùng trong biểu đồ Venn duy nhất một lần.

Công thức trên có thể viết gọn thành

| ⋃ i = 1 n A i | = ∑ k = 1 n ( − 1 ) k + 1 ( ∑ 1 ⩽ i 1 < ⋯ < i k ⩽ n | A i 1 ∩ ⋯ ∩ A i k | ) {\displaystyle \left|\bigcup _{i=1}^{n}A_{i}\right|=\sum _{k=1}^{n}(-1)^{k+1}\left(\sum _{1\leqslant i_{1}<\cdots <i_{k}\leqslant n}|A_{i_{1}}\cap \cdots \cap A_{i_{k}}|\right)}

hoặc

| ⋃ i = 1 n A i | = ∑ ∅ ≠ J ⊆ { 1 , … , n } ( − 1 ) | J | + 1 | ⋂ j ∈ J A j | . {\displaystyle \left|\bigcup _{i=1}^{n}A_{i}\right|=\sum _{\emptyset \neq J\subseteq \{1,\ldots ,n\}}(-1)^{|J|+1}\left|\bigcap _{j\in J}A_{j}\right|.}

Nói bằng từ, để đếm số phần tử của hợp hữu hạn các tập hợp hữu hạn, trước hết lấy tổng các lực lượng của các tập hợp đó, rồi trừ đi lực lượng của tập các phần tử xuất hiện ít nhất trong hai tập hợp, sau đó thêm lại số phần tử xuất hiện trong ít nhất ba tập hợp và tiếp tục như thế. Quá trình luôn dừng là bởi không có phần tử nào xuất hiện nhiều hơn số tập hợp đang xét. (Ví dụ chẳng hạn, nếu n = 4 , {\displaystyle n=4,} thì không có phần tử nào xuất hiện trong nhiều hơn 4 {\displaystyle 4} tập hợp)

Trong ứng dụng, ta thường dùng nguyên lý này dưới dạng sử dụng phần bù. Tức là, gọi S là tập phổ dụng hữu hạn chứa tất cả các tập Ai và ta gọi A i ¯ {\displaystyle {\bar {A_{i}}}} là phần bù của Ai trong S, theo luật De Morgan, ta có

| ⋂ i = 1 n A i ¯ | = | S − ⋃ i = 1 n A i | = | S | − ∑ i = 1 n | A i | + ∑ 1 ⩽ i < j ⩽ n | A i ∩ A j | − ⋯ + ( − 1 ) n | A 1 ∩ ⋯ ∩ A n | . {\displaystyle \left|\bigcap _{i=1}^{n}{\bar {A_{i}}}\right|=\left|S-\bigcup _{i=1}^{n}A_{i}\right|=|S|-\sum _{i=1}^{n}|A_{i}|+\sum _{1\leqslant i<j\leqslant n}|A_{i}\cap A_{j}|-\cdots +(-1)^{n}|A_{1}\cap \cdots \cap A_{n}|.}

Một phiên bản khác của công thức trên được phát biểu như sau: gọi P1, ..., Pn là danh sách các tính chất mà mỗi phần tử thuộc tập hợp S có thể có hoặc không có, khi đó nguyên lý bao hàm-loại hàm cho phép đếm số các phần tử thuộc S và không có tính chất nào trong các tính chất trên bằng cách đặt Ai là tập con của tập các phần tử thuộc S và có tính chất Pi và sử dụng nguyên lý trên trong dạng phần bù. Phiên bản này bắt nguồn từ J. J. Sylvester.[1]